This invention relates to devices handling integer arithmetic, specifically to the exponentiation and modular reduction of large integers.
Modular reduction is closely related to division. Suppose N and P are positive integers. Then long division as taught in elementary school gives a quotient Q and remainder R. These are the unique nonnegative integers satisfying, EQU N=QP+R EQU R&lt;P
For example, if N=25 and P=7 then Q=3 and R=4. This is the computation that one does to deduce that 25/7=3 4/7. In this context, P is also called the modulus, and N is said to be reduced to the residue R.
Exponentiation is the operation of raising a number (called the base) to a power. The base is multiplied by itself some number of times, that number being called the exponent. For example, 5 raised to the 2-nd power is 5.sup.2 =5.multidot.5=25 and 5 raised to the 6-th power is 5.sup.6 =5.multidot.5.multidot.5.multidot.5.multidot.5.multidot.5=15625. Modular exponentiation combines raising to a power with with modular reduction. For example, 5.sup.2 reduced with modulus 7 is 4.
In certain applications such as cryptography, the number P is a very large integer and these exponentiations and reductions must be applied to other large integers. Such large integers may have hundreds of decimal digits. See for example reference 7 for the utility of such computations. In that context, the inputs are usually messages or cryptographic keys. Since any digital input signal may be regarded as a large integer, the description of this invention refers to the inputs as integers.
Large integers are ordinarily stored in an array of registers, and in binary form. The registers may be visualized sequentially as one gigantic binary integer, with the register at one end being the most significant part, and the register at the other end being the least significant. For example, the number 1234 has 1 as its most significant digit, and 4 as its least significant digit. If a register holds one decimal digit, then the number could be stored in an array of four registers.
Operations are performed by a central processing unit, which usually has an adder, a subtracter, a multiplier, and sometimes a divider. Each such unit can only perform an operation on a quantity if it fits into a register. There is also some mechanism for handling a carry, the result of an arithmetic overflow in an add or a subtract. The result of a multiply ordinarily requires two registers, and does not involve a carry.
It is well known how to build an array adder or an array subtracter. The array adder adds each register of one input with the corresponding register of the other, starting with the least significant register. The overflow, or carry, in incorporated in to the next add. An array subtracter is similar, with the carry sometimes called a borrow in this context. See reference 8 for details. It has a thorough exposition of the prior art relating to the subject of this invention.
An array multiplier can be built from multipliers and adders. Such a device can multiply two register arrays, putting the product in a third register array. In the prior art, this is usually done with a multiplier and an adder with carry. The output register array is initialized with zeros, and acts as an accumulator. The multiplier scans each register of each input, computing products. The products are added to the output register array, with carries propagated accordingly.
Reference 8 presents an alternative array multiplier. Each product is computed in two registers. Only one is added into the output array, with the carry incorporated back into the other register. That latter register is kept with the multiplier so it can be either incorporated into the next product or later added into the output. This array multiplier is an improvement in that it avoids carry propagation, but requires a more complex multiplier having an extra register.
When multiplying fractional quantities, reference 8 suggests discarding some of the products to give an approximate answer. However the method is not recommended for use when multiplying integers, because on rare occasions a lost carry can make all of the digits in the answer wrong if even just one product is omitted. Integer arithmetic normally requires all digits to be correct.
In the prior art, modular reduction is performed by a divider, if the value fits in a register. A divider typically uses repeated subtractions. While some dividers are very clever and efficient, they are slower than multipliers.
Modular reduction of larger integers is performed by a array divider, which often operates by repeated subtraction. If a register divider is available, then an improved method is available, and is described in reference 8. It is similar to long division as taught in elementary school, and consists of repeated divisions, multiplications, and subtractions.
For very large integers (thousands or more decimal digits), reference 2 gives more efficient methods for computing products and inverses. These use approximate inverses in the context of Fourier transform multipliers, but not in conjunction with the type of array multipliers used in this invention.
Modular exponentiation appears extraordinarily complex, but there are a couple of standard tricks which dramatically simplify the process. These tricks are to use repeated squaring and to reduce after each multiply. If, for example, the modulus is 7, then 5.sup.6 could be reduced by calculating 5.sup.6 =15625, and dividing by 7 to get 2232 1/7, so the residue is 1. With much larger numbers, such a direct calculation is impractical. The clever method is to repeatedly square 5. 5.sup.2 =25 has residue 4. Squaring again, 5.sup.4 =(5.sup.2).sup.2 has the same residue as 4.sup.2 =16, which is 2 since 16/7=2 2/7. Thus 5.sup.6 =5.sup.4 .multidot.5.sup.2 has the same residue as 2.multidot.4=8, ie, 1.
The method of modular exponentiation used is this example is perfectly general, and widely used. The binary representation of the exponent is precisely the recipe for deciding which squares must be multiplied together. A modular reduction at each stage prevents the numbers from getting too large. A modular exponentiation device can be built out of a modular reduction device, an array shifter, and an array multiplier. The array multiplier repeatedly squares the base. The array shifter repeatedly examines the bits in the exponent, one at a time, and conditionally signals the array multiplier to do another product. The modular reduction device is applied to the result of each multiply. The method is quite efficient, but this invention provides an improvement.
In the prior art, there are various methods for organizing the sequence of powers in a manner which reduces the number of multiplications. One method is to store the repeated squarings of the base in a table. For example, if powers of 5 are needed, then 5.sup.2, 5.sup.4, 5.sup.8, . . . can be stored in a table. Another method is to use the ternary (rather than binary) expansion of the exponent. Other number representations are also possible. For details, see Knuth, reference 8.